package baseTest;

public class minDistance {
    public static void main(String[] args) {
        String word1 = "horse";
        String word2 = "ros";
        System.out.println(process(word1,word2));
    }
    public static int process(String word1,String word2){
        int[][] ans = new int[word1.length()+1][word2.length()+1];
        for (int i = 0; i < ans.length; i++) {
            ans[i][0] = i;
        }
        for (int j = 0; j < ans[0].length; j++) {
            ans[0][j] = j;
        }
        for (int k = 1; k < ans.length; k++) {
            for (int l = 1; l <ans[0].length; l++) {
                ans[k][l] = Math.min(Math.min(ans[k-1][l],ans[k][l-1]),ans[k-1][l-1])+1;
                if (word1.charAt(k-1) == word2.charAt(l-1)){
                    ans[k][l] = Math.min(ans[k][l],ans[k-1][l-1]);
                }
            }
        }
        return ans[word1.length()][word2.length()];
    }
}
